/*
 * @lc app=leetcode.cn id=968 lang=cpp
 *
 * [968] 监控二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
    int res = 0;
    int traversal(TreeNode *root)
    {
        if (root == NULL)
        {
            return 2; //空节点都认为是被覆盖的
        }
        int left = traversal(root->left);
        int right = traversal(root->right);
        if (left == 2 && right == 2)
        {
            //如果子节点都被覆盖 那么当前节点没有被覆盖
            return 3;
        }
        if (left == 3 || right == 3)
        {
            //左右子节点只要有一个没有被覆盖 那么就需要摄像头
            res++;
            return 1;
        }
        if (left == 1 || right == 1)
        {
            //左右子节点只要有一个是摄像头 那么当前节点被覆盖
            return 2;
        }
        return -1;
    }
    int minCameraCover(TreeNode *root)
    {
        //监控二叉树 这里的贪心就是从下往上 因为叶子结点是最多的 叶子结点不能装摄像头
        //后序遍历从下往上 叶子节点不装 叶子结点父节点开始装摄像头
        //需要判断当前节点处于什么状态
        //应该分为以下几个状态 1.有摄像头 2.被覆盖 3没有覆盖
        //叶子结点应该是处于被覆盖 也就是说遍历到子节点为空的时候 设当前节点为被覆盖状态

        //遍历树 获取摄像头个数
        if (traversal(root) == 3)
        {
            //root无覆盖
            res++;
        }
        return res;
    }
};
// @lc code=end
